package com.markus.code.剑指offer;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/31 13:31
 * todo: 树的子结构(未做出)
 */
public class IsSubStructure {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A==null || B == null){
            return false;
        }
        boolean flag = false;
        if (A.val == B.val){
            flag = process(A,B);
        }
        if (!flag){
            flag = isSubStructure(A.left,B);
        }
        if (!flag){
            flag = isSubStructure(B.left,B);
        }
        return flag;

    }
    private boolean process(TreeNode A,TreeNode B){
        if (B == null){
            return true;
        }
        if (A == null){
            return false;
        }
        if (A.val != B.val){
            return false;
        }
        return process(A.left,B.left) && process(A.right,B.right);
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(3);
        A.left = new TreeNode(4);
        A.right = new TreeNode(5);
        A.left.left = new TreeNode(1);
        A.left.right = new TreeNode(2);
        TreeNode B = new TreeNode(4);
        B.left = new TreeNode(1);
        IsSubStructure demo = new IsSubStructure();
        System.out.println(demo.isSubStructure(A,B));
    }
}
